package com.heima.leetcode.algorithm.exhaustive;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 零钱兑换1 322
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/15 16:20
 */
public class ChangeOne {
    static int min = -1; // 需要的最少硬币数

    /**
     * <h3>方法一，穷举法</h3>
     *
     * @param amount 目标金额
     * @param coins  硬币的面额
     * @return 硬币组合的总数
     */
    public int coinChange(int amount, int[] coins) {
        coins = reverseOrderSort(coins);
        coinChange(0, amount, coins, new AtomicInteger(-1));
        int result = min;
        // 重置为-1
        min = -1;
        return result;
    }

    /**
     * <h3>方法二，穷举法，打印出所有情况</h3>
     * @param amount 目标金额
     * @param coins 硬币面额
     * @return 硬币组合的总数
     */
    public int coinChangeAndPrint(int amount, int[] coins) {
        coins = reverseOrderSort(coins);
        coinChange(0, amount, coins, new LinkedList<>(),new AtomicInteger(-1), true);
        int result = min;
        // 重置为-1
        min = -1;
        return result;
    }

    /**
     * 倒序排序数组
     * @param coins 硬币面额
     * @return 排序后的结果
     */
    private static int[] reverseOrderSort(int[] coins) {
        coins = Arrays.stream(coins)
                .boxed()
                .sorted(Comparator.reverseOrder())
                .mapToInt(Integer::intValue)
                .toArray();
        return coins;
    }

    /*

       思想：
       从数组索引0开始，每次选当前索引的硬币放到组合中去，
       看当前组合能不能满足目标金额条件，
       如果满足，则返回1，结束递归，
       如果不满足并且剩余目标金额 < 0，则返回0，结束递归
       如果不满足并且剩余目标金额 > 0，则继续递归组合：
       接下来的组合方式就是本轮递归选入组合的硬币在数组中的索引开始（包含自己）
       让当前硬币对应索引开始的所有硬币独立加入到当前组合中，每一个硬币就是一种情况，（好马不吃回头草）
       重复以上逻辑
       值得注意的是当发现某轮递归满足条件，返回的时候，其实应该当把该次递归选择的硬币踹出组合，好进行父级递归
       因为递归中用amount记录剩余目标金额，递归具有先天的优势，它自己返回父级递归的时候就会把这个硬币踹出去（amount恢复到原来的值）

       假设amount = 5，coins = {1,2,5}
       那么递归过程：
         change(0, 5, coins)
             change(0, 4, coins)
                change(0, 3, coins)
                    change(0, 2, coins)
                        change(0, 1, coins)
                            change(0, 0, coins) 1
                            change(1,-1, coins) 0
                            change(2,-4, coins) 0
                        change(1, 0, coins) 1
                        change(2,-3, coins) 0
                    change(1, 1, coins)
                        change(1,-1, coins) 0
                        change(2,-4, coins) 0
                    change(2,-2, coins) 0
                change(1, 2, coins)
                    change(1, 0, coins) 1
                    change(2,-3, coins) 0
                change(2,-1, coins) 0
             change(1, 3, coins)
                change(1, 1, coins)
                    change(1,-1, coins) 0
                change(2,-2, coins) 0
             change(2, 0, coins) 1

          假设amount = 5，coins = {5,2,1}
          那么递归过程：
            change(0, 5, coins)
                change(0, 0, coins) 1
                change(1, 3, coins)
                    change(1, 1, coins)
                        change(1,-1, coins) 0
                        change(2, 0, coins) 1
                    change(2, 2, coins)
                        change(2, 1, coins)
                            change(2, 0, coins) 1
                change(2, 4, coins)
                    change(2, 3, coins)
                        change(2, 2, coins)
                            change(2, 1, coins)
                                change(2, 0, coins) 1

          到这里也可以发现：先往组合里面放大的，再放小的，可以规避很多无效的情况（主要是减少很多小的组成大的的情况），减少递归次数
     */

    /**
     * 递归求解
     *
     * @param index  已经选好的硬币下标
     * @param amount 剩下的目标金额
     * @param coins  硬币面额
     * @param length 组合里面选的硬币数量
     * @return 硬币组合的总数
     */
    private int coinChange(int index, int amount, int[] coins, AtomicInteger length) {
        // 记录当前组合里面选的硬币数量
        int len = length.incrementAndGet();
        // 统计当前组合开头的所有满足条件的组合的总数
        int count = 0;
        // 待组合的目标金额为0，说明当前选出来的硬币符合要求，返回1
        if (amount == 0) {
            if (min == -1 || len < min) {
                min = len;
            }
            count++;
        }
        // 目标金额小于0，说明当前选出来的硬币组合无法满足目标金额，结束递归，返回0
        else if (amount < 0) {
            length.getAndDecrement();
            return 0; // 一样的，为了不爆黄
        }
        // 目标金额大于0，说明当前选出来的硬币组合无法满足目标金额，继续递归，返回所有组合的总数
        else {
            // 思想：穷举，列出所有有可能的组合
            for (int i = index; i < coins.length; i++) {
                // 从当前索引的硬币开始依次选择硬币进行组合，如果满足则返回1，剩余小于0则返回，剩余大于0仍要继续递归
                count += coinChange(i, amount - coins[i], coins, length);
            }
        }
        // 递归结束后，把当前组合的硬币数量减一
        length.getAndDecrement();
        // 返回所有组合的总数
        return count;
    }

    /**
     * 找出所有可能以及打印出所有情况
     * @param index 当前选的元素的数组索引
     * @param amount 当前要组合的目标金额
     * @param coins 硬币面额
     * @param stack 栈，用于存储当前组合的硬币
     * @param length 组合里面选的硬币数量
     * @param isFirst 是否是第一次调用，如果是则不输出栈
     * @return 返回符合条件的组合的总数
     */
    private int coinChange(int index, int amount, int[] coins, LinkedList<Integer> stack, AtomicInteger length, boolean isFirst) {
        // 记录当前组合里面选的硬币数量
        int len = length.incrementAndGet();
        // 记录当前组合里面选的硬币数量
        int count = 0;
        // 添加当前硬币
        if (!isFirst) {
            stack.push(coins[index]);
        }
        // 待组合的目标金额为0，说明当前选出来的硬币符合要求，返回1
        if (amount == 0) {
            // 更新所需硬币的最小个数
            if (min == -1 || len < min) {
                min = len;
            }
            // 打印当前组合
            System.out.print("有解：");
            print(stack);
            count++;
        }
        // 目标金额小于0，说明当前选出来的硬币组合无法满足目标金额，结束递归，返回0
        else if (amount < 0) {
            // 打印当前组合
            System.out.print("无解：");
            print(stack);
        }
        // 目标金额大于0，说明当前选出来的硬币组合无法满足目标金额，继续递归，返回所有组合的总数
        else {
            // 思想：穷举，列出所有有可能的组合
            for (int i = index; i < coins.length; i++) {
                // 从当前索引的硬币开始依次选择硬币进行组合，如果满足则返回1，剩余小于0则返回，剩余大于0仍要继续递归
                count += coinChange(i, amount - coins[i], coins, stack, length, false);
            }
        }
        // 将当前组合的最后一个元素弹出
        if (!stack.isEmpty()) {
            stack.pop();
        }
        // 递归结束后，把当前组合的硬币数量减一
        length.getAndDecrement();
        return count;
    }

    /**
     * 打印栈
     * @param stack 栈
     */
    private void print(LinkedList<Integer> stack) {
        System.out.print("[");
        ListIterator<Integer> iterator = stack.listIterator(stack.size());
        while (iterator.hasPrevious()) {
            System.out.print(" " + iterator.previous());
        }
        System.out.println(" ]");
    }
}
